package fr.cephb.util;

import java.util.Comparator;
import java.util.Random;

public class QuickSort
	{
	private Comparator<byte[]> comparator;
	private int sizeof;
	private byte swap_array[]=null;
	private byte cmp_array_1[]=null;
	private byte cmp_array_2[]=null;
	
	public QuickSort(int sizeof,Comparator<byte[]> comparator)
		{
		if(sizeof<=0) throw new IllegalArgumentException("Bad sizeof:"+sizeof);
		this.sizeof=sizeof;
		this.comparator=comparator;
		this.swap_array=new byte[sizeof];
		this.cmp_array_1=new byte[sizeof];
		this.cmp_array_2=new byte[sizeof];
		}
	public QuickSort(int sizeof)
		{
		this(sizeof,null);
		}
	
	
	 public void shuffle(byte[] buffer)
		 {
		 Random rand= new Random();
	     int N = buffer.length/sizeof;
	     for (int i = 0; i < N; i++)
	    	 {
	         int r = i + rand.nextInt(N-i);   // between i and N-1
	         exchange(buffer, i, r);
	     	}
     	}	
	
	private void exchange(byte buffer[],int i, int j)
		{
		System.arraycopy(buffer, i*sizeof, this.swap_array, 0, sizeof);
		System.arraycopy(buffer, j*sizeof, buffer, i*sizeof, sizeof);
		System.arraycopy(this.swap_array, 0, buffer, j*sizeof, sizeof);
		}
	
	
	private int compare(
		final byte buffer[],
		final int index1,
		final int index2)
		{
		final int offset_1= index1*sizeof;
		final int offset_2= index2*sizeof;
		if(this.comparator!=null)
			{
			System.arraycopy(buffer, offset_1, this.cmp_array_1, 0, sizeof);
			System.arraycopy(buffer, offset_2, this.cmp_array_2, 0, sizeof);
			return comparator.compare(this.cmp_array_1,this.cmp_array_2);
			}
		int i=0;
		while(i<sizeof)
			{
			int a=buffer[offset_1+i];
			int b=buffer[offset_2+i];
			if(a!=b) return a-b;
			i++;
			}
		return 0;
		}


	
	
	public void quicksort(byte buffer[])
		{
		shuffle(buffer);//avoid worst case else might lead to stack overflow error of 'quicksort' 
		quicksort(buffer,0,(buffer.length/sizeof)-1);
		}
	
	public void quicksort(byte buffer[],final int low,final int high)
		{
		if(high<=low) return;
		int i= partition(buffer,low,high);
		quicksort(buffer,low,i-1);
		quicksort(buffer,i+1,high);
		}
	
	 private int partition(byte[] a, int left, int right)
		 {
	     int i = left - 1;
	     int j = right;
	     while (true)
	    	 {
	         while(compare(a,++i, right)<0)      // find item on left to swap
	             {                               // a[right] acts as sentinel
	             //nothing
	             }
	         while (compare(a,right,--j)<0)      // find item on right to swap
	             {
	             if (j == left) break;           // don't go out-of-bounds
	             }
	         if (i >= j) break;                  // check if pointers cross
	        exchange (a, i, j);                      // swap two elements into place
	     	}
	     exchange(a, i, right);                      // swap with partition element
	     return i;
		 }
	
	public static void main(String[] args)
		{
		Random rand= new Random();
		StringBuilder b= new StringBuilder();
		for(int i=0;i< 100;i++)
			{
			for(int j=0;j<10;++j)
				{
				b.append((char)('A'+rand.nextInt(26)));
				}
			b.append(' ');
			}
		byte array[]=b.toString().getBytes();
		QuickSort q= new QuickSort(11);
		q.quicksort(array);
		System.err.println(new String(array));
		q= new QuickSort(11,new Comparator<byte[]>()
			{
			@Override
			public int compare(byte[] o1, byte[] o2)
				{
				return new String(o2).compareToIgnoreCase(new String(o1));
				}
			});
		q.shuffle(array);
		q.quicksort(array);
		System.err.println(new String(array));
		}
	
	}
